package com.sun;

/**
 * https://leetcode.cn/problems/longest-common-prefix/
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""。
 */
public class Test14最长公共前缀 {
    public static void main(String[] args) {
        String[] strs = new String[]{"aaa","aa","aaa"};
        System.out.println("abcaaacb".matches("^abc.*"));
        String s = longestCommonPrefix3(strs);
        System.out.println(s);
    }
    /**
     * 方法一：自己
     */
    public static String longestCommonPrefix1(String[] strs){
        for (int i = 1; i <= strs[0].length(); i++) {
            String str = strs[0].substring(0,i);
            String reg = "^"+str + ".*";
            for (int j = 1; j < strs.length; j++) {
                if (!strs[j].matches(reg)){
                    return str.substring(0,str.length()-1);
                }
            }
        }
        return strs[0];
    }
    /**
     *方法2：自己,纵向比较；跟力扣官方一样；
     */
    public static String longestCommonPrefix2(String[] strs){
        if (strs.length == 0) return "";
        for (int i = 0; i < strs[0].length(); i++) {
            for (int j = 1; j < strs.length; j++) {
                if (i > strs[j].length()-1 || strs[0].charAt(i) != strs[j].charAt(i)){
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];
    }

    /**
     * 方法3：力扣官方，横向比较
     */
    public static String longestCommonPrefix3(String[] strs){
        String res = strs[0];
        for (int i = 1; i < strs.length; i++){
            res = longestCommonPrefix3(res,strs[i]);
            if (res.isEmpty()){
                break;
            }
        }
        return res;
    }

    public static String longestCommonPrefix3(String str1, String str2){
        int min = Math.min(str1.length(), str2.length());
        int i = 0;
        while (i < min && str1.charAt(i)==str2.charAt(i)){
            i++;
        }
       return str1.substring(0,i);
    }

}
